package april.test_4_21;

public class Test {
    boolean flag = false;
    int t;
    public boolean kInArray (int k, int target) {
        // write code here
        t = target;
        if(k > t) {
            if(k < 0 && t < 0) {
                dfs(k);
            } else {
                dfs2(k);
            }
        } else {
            dfs2(k);
        }
        if(flag) {
            return true;
        }
        return false;
    }
    public void dfs(int x) {
        if(x < t || flag) return;
        if(x == t) {
            flag = true;
            return;
        }
        if((x - 1) % 2 == 0) dfs((x - 1) / 2);
        if((x - 1) % 3 == 0) dfs((x - 1) / 3);
        return;
    }
    public void dfs2(int x) {
        if(x > t || flag ) {
            return;
        } else if( x == t) {
            flag = true;
            return;
        }else {
            dfs2(x * 2 + 1);
            dfs2(x * 3 + 1);
        }
        return;
    }
}
